package niuke.test;

import java.util.Scanner;

/**
 牛牛有两个字符串（可能包含空格）,牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。

 abcde
 abgde
 */
public class MaxSubSeq {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str1 = "af22b32f34bbfbaab";
        String str2= "afa3fbbdbcc";

//        dp[i][j]  str1__(0...i]    str2__(0...j]   的最长长度
        int [][]dp = new int[str1.length()][str2.length()];

        for (int i = 0; i < str1.length(); i++) {//str1__(0...i]   str2__[0]
            if(str1.charAt(i)==str2.charAt(0))
                dp[i][0]=1;
        }

        for (int j = 0; j < str2.length(); j++) {//str1__[0]   str2__(0...i]
            if(str2.charAt(j)==str1.charAt(0))
                dp[0][j]=1;
        }


        int a ,b,c;
        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                        a = dp[i-1][j-1];//不以 i,j结尾
                        b = dp[i-1][j];//以j结尾
                        c = dp[i][j-1];//以i结尾
                        dp[i][j] = Math.max( Math.max(a,b)  , c);

                if(str1.charAt(i)==str2.charAt(j))//以i,j结尾
                    dp[i][j] = dp[i-1][j-1]+1;

            }
            
        }
        System.out.println(dp[str1.length()-1][str2.length()-1]);




    }
}